package com.c2b.algorithm.newcoder.hash;

import java.util.HashMap;
import java.util.Map;

/**
 * <a href="https://www.nowcoder.com/practice/20ef0972485e41019e39543e8e895b7f?tpId=295&tqId=745&ru=%2Fpractice%2Fc215ba61c8b1443b996351df929dc4d4&qru=%2Fta%2Fformat-top101%2Fquestion-ranking&sourceUrl=%2Fexam%2Foj">两数之和</a>
 * <p>给出一个整型数组 numbers 和一个目标值 target，请在数组中找出两个加起来等于目标值的数的下标，返回的下标按升序排列。
 * （注：返回的数组下标从1开始算起，保证target一定可以由数组里面2个数字相加得到）</p>
 * <p>
 * 数据范围：2≤len(numbers)≤10^5，−10≤numbers[i]≤10^9，0≤target≤10^9<br>
 * 要求：空间复杂度O(n)，时间复杂度O(nlogn)
 * </p>
 *
 * @author c2b
 * @since 2023/3/14 16:13
 */
public class BM0050TwoSum_S {

    public int[] twoSum(int[] numbers, int target) {
        // numbers数组中元素最少为2个。不需要做健壮性校验
        // key:数值 value:对应在数组中的索引
        Map<Integer, Integer> map = new HashMap<>();
        for (int currIndex = 0; currIndex < numbers.length; currIndex++) {
            int number = numbers[currIndex];
            if (map.containsKey(target - number)) {
                Integer index = map.get(target - number);
                return currIndex > index ? new int[]{index + 1, currIndex + 1} : new int[]{currIndex + 1, index + 1};
            }
            map.put(number, currIndex);
        }
        return new int[0];
    }

    public static void main(String[] args) {
        BM0050TwoSum_S bm0050TwoSum_s = new BM0050TwoSum_S();
        for (int i : bm0050TwoSum_s.twoSum(new int[]{20, 70, 110, 150}, 90)) {
            System.out.println(i);
        }
    }
}
